package lc;
import java.util.*;

import org.junit.*;

import util.BracketUtils;
public class Ex210 {
    class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            int[] res = new int[numCourses];
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < numCourses; i++) set.add(i);
            Map<Integer, List<Integer>> map  = new HashMap<>();
            Map<Integer, Integer> needs = new HashMap<>();
            for (int i = 0; i < prerequisites.length; i++) {
                set.remove(prerequisites[i][0]);
                needs.put(prerequisites[i][0], needs.getOrDefault(prerequisites[i][0], 0) + 1);
                if (map.containsKey(prerequisites[i][1])) {
                    map.get(prerequisites[i][1]).add(prerequisites[i][0]);
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(prerequisites[i][0]);
                    map.put(prerequisites[i][1], list);
                }
            }
            int idx = 0;
            Queue<Integer> queue = new LinkedList<>(set);
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                res[idx++] = cur;
                if (!map.containsKey(cur)) continue;
                List<Integer> nexts = map.get(cur);
                for (int next: nexts) {
                    int need = needs.get(next);
                    if (need == 1) {
                        needs.remove(next);
                        queue.offer(next);
                    } else {
                        needs.put(next, need - 1);
                    }
                }
                map.remove(cur);
            }
            return idx == numCourses ? res : new int[0];
        }
    }
    @Test
    public void test() {
        Solution s = new Solution();
        int[][] nums = BracketUtils.to2DArray("[[1,0],[2,0],[3,1],[3,2]]");
        System.out.println(Arrays.toString(s.findOrder(4, nums)));
    }
}
